//给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 
//
// 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct
//-characters 相同 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "bcabc"
//输出："abc"
// 
//
// 示例 2： 
//
// 
//输入：s = "cbacdcbc"
//输出："acdb" 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 由小写英文字母组成 
// 
// Related Topics 栈 贪心算法 字符串 
// 👍 290 👎 0

package com.leetcode.editor.cn;

//Java：去除重复字母
class P316RemoveDuplicateLetters {
    public static void main(String[] args) {
        Solution solution = new P316RemoveDuplicateLetters().new Solution();
        // TO TEST
        String s = "ecbacba";
        System.out.println(solution.removeDuplicateLetters(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            //记录每个字母最后出现的位置
            int[] lastAppearPosition = new int[26];
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                lastAppearPosition[chars[i] - 'a'] = i;
            }
            boolean[] isContain = new boolean[26];
//            Stack<Character> stack = new Stack<>();
            char[] stack = new char[26];
            //优化，用数组模拟栈，避免栈动态扩容
            //数组的最顶端的元素位置
            int top = -1;
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                //栈不为空,且已经包含
//                    if (stack.contains(c)) {优化判断栈是否包含当前元素
                if (!isContain[c - 'a']) {
                    //如过栈不为空，且当前元素小于栈顶元素，且栈顶元素不是最后一次出现，弹出栈顶元素，继续比较
                    while (top !=-1  && c < stack[top] && i < lastAppearPosition[stack[top] - 'a']) {
                        isContain[stack[top--] - 'a'] = false;
                    }
                    isContain[c - 'a'] = true;
                    stack[++top] = c;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= top; i++) {
                sb.append(stack[i]);
            }
            return sb.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}